CodeWars 題目

Link

難度

5 kyu

題目

不需要保持連續，找到最長的子序列。
譬如 "abcdef" , "acf"，雖然並非連續，但都可以拼出 acf。

思路

用兩個變數紀錄字串的索引，比對到一樣的，就一起 ++。
如果比對到不同的值，只 + 一邊；迴圈的停止條件是各自都算到盡頭。

實作

function LCS(x, y) {
   let Xorder = {}
   let Yorder = {}
   let loop = x.length < y.length ? x : y;
   let compare = x.length < y.length ? Yorder : Xorder;
   let result = "";
   for (let i = 0; i < x.length; i++) {
      if (!Xorder[x[i]]) {
         Xorder[x[i]] = [];
      }
      Xorder[x[i]].push(i + 1)
   }
   for (let i = 0; i < y.length; i++) {
      if (!Yorder[y[i]]) {
         Yorder[y[i]] = [];
      }
      Yorder[y[i]].push(i + 1)
   }
   for (let i = 0; i < loop.length; i++) {
      if (compare[loop[i]]) {
         let index = compare[loop[i]].filter(item => item >= i + 1);
         if (index.length) result += loop[i];
      }
   }
   return result;
}

如果兩個字串有長度差異，優先迭代短的去比對長字串是否能夠組成。
loop 以及 compare 分別記錄要被 loop 以及要被比對的字串組成的物件。

跑兩次迴圈，紀錄兩個字串每個數字出現的位置；最終結果會在 compare 中被使用。
並且由於一個數字出現可能不只一次，用陣列類型。

迭代 loop 字串，如果能在比對物件中被找到，取得該元素之中的 index 陣列，並用 filter 去確保元素的出現順序是正確的，不能小於目前的 index；最後輸出拼接的結果 result。

他人的解法

function LCS(x, y) {
   x = x.split("");
   return y.split("").filter((item) => {
      if (x.indexOf(item) !== -1) {
         return x.splice(0, x.indexOf(item) + 1);
      }
   }).join("");
}

分別都將兩個字串參數都轉為陣列，迭代 y 字串後調用 filter 過濾。
如果迭代到的字元能在 x 之中被找到，用 splice 刪除 x 陣列元素，但會返回到 filter。

最後過濾的結果，用 join 轉為字串。

心得

看到自己的程式碼落落長有點打擊(つд⊂)
用了三個 for 迴圈真是要不得